package main.面试金典第六版;

import java.util.*;

public class Interview16 {
    public static void main(String[] args) {
        System.out.println("面试题16.01：交换数字");
        System.out.println("面试题16.02：单词频率");
        System.out.println("面试题16.03：交点");
        System.out.println("面试题16.04：井字游戏");
        System.out.println("面试题16.05：阶乘尾数");
        System.out.println("面试题16.06：最小差");
        System.out.println("面试题16.07：最大数值");
        System.out.println("面试题16.08：整数的英语表示");
        System.out.println("面试题16.09：运算");
        System.out.println("面试题16.10：生存人数");
        System.out.println("面试题16.11：跳水板");
        System.out.println("面试题16.13：平分正方形");
        System.out.println("面试题16.14：最佳直线");
        System.out.println("面试题16.15：珠玑妙算");
        System.out.println("面试题16.16：部分排序");
        System.out.println("面试题16.17：连续数列");
        System.out.println("面试题16.18：模式匹配");
        System.out.println("面试题16.19：水域大小");
        System.out.println("面试题16.20：T9键盘");
        System.out.println("面试题16.21：交换和");
        System.out.println("面试题16.22：兰顿蚂蚁");
        System.out.println("面试题16.24：数对和");
        System.out.println("面试题16.25：LRU缓存");
        System.out.println("面试题16.26：计算器");
    }
}

class Interview_16_01{
    public int[] swapNumbers(int[] numbers) {
        numbers[0]=numbers[0]^numbers[1];
        numbers[1]=numbers[0]^numbers[1];
        numbers[0]=numbers[0]^numbers[1];
        return numbers;
    }
}

class Interview_16_02{
    Map<String,Integer> map;
    public Interview_16_02(String[] book) {
        map=new HashMap<>();
        for (String curStr : book) map.put(curStr,map.getOrDefault(curStr,0)+1);
    }

    public int get(String word) {
        if (map.containsKey(word)) return map.get(word);
        else return 0;
    }
}

class Interview_16_03{
    public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
        return null;
    }
}

class Interview_16_04{
    public String tictactoe(String[] board) {
        int N = board.length;
        int rows = 0, cols = 0, dig1 = 0, dig2 = 0;
        boolean f = false;//判断是否有空格
        for (int i = 0; i < N; i++) {
            rows = 0;
            cols = 0;
            dig1 += board[i].charAt(i);
            dig2 += board[i].charAt(N - 1 - i);
            for (int j = 0; j < N; j++) {
                rows += board[i].charAt(j);
                cols += board[j].charAt(i);
                if (board[i].charAt(j) == ' ') f = true;
            }
            if (rows == 'X' * N || cols == 'X' * N) return "X";//判断行列
            else if (rows == 'O' * N || cols == 'O' * N) return "O";
        }
        if (dig1 == 'X' * N || dig2 == 'X' * N) return "X";
        if (dig1 == 'O' * N || dig2 == 'O' * N) return "O";
        if (f) return "Pending";
        return "Draw";
    }
}

class Interview_16_05{
    public int trailingZeroes(int n) {
        int count=0;
        while (n!=0) {
            n/=5;
            count+=n;
        }
        return count;
    }
}

class Interview_16_06{
    public int smallestDifference(int[] a, int[] b) {
//        int[][] arr=new int[a.length+b.length][];
//        int index=0,minDiff=Integer.MAX_VALUE;
//        for (int i=0;i<a.length;i++) {//合并两数组
//            int[] temp=new int[2];
//            temp[1]=1;
//            temp[0]=a[i];
//            arr[index++]=temp;
//        }
//        for (int i=0;i<b.length;i++) {
//            int[] temp=new int[2];
//            temp[0]=b[i];
//            temp[1]=2;
//            arr[index++]=temp;
//        }
//        Arrays.sort(arr, new Comparator<int[]>() {//合并后排序
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                if (o1[0]!=o2[0]) return o1[0]-o2[0];
//                return 0;
//            }
//        });
//        for (int i=1;i< arr.length;i++) {//寻找相邻且来自不同数组的元素并计算差值
//            if (arr[i][1]!=arr[i-1][1]) minDiff=Math.min(minDiff,arr[i][0]-arr[i-1][0]);
//        }
//        return minDiff;
        long minDiff=Long.MAX_VALUE;
        Arrays.sort(a);
        Arrays.sort(b);
        int i=0,j=0;
        while (i<a.length&&j<b.length) {
            if (a[i]==b[j]) {
                minDiff=0;
                break;
            }
            else if (a[i]>b[j]) {
                minDiff=Math.min(minDiff,(long)a[i]-(long)b[j]);
                j++;
            }else {
                minDiff=Math.min(minDiff,(long)b[j]-(long)a[i]);
                i++;
            }
        }
        return (int)minDiff;
    }
}

class Interview_16_07{
    public int maximum(int a, int b) {
        return a>b ? a : b;
    }
}

class Interview_16_08{
    public String numberToWords(int num) {
        return " ";
    }
}

class Interview_16_09{
    public Interview_16_09() {

    }

    public int minus(int a, int b) {
        return (int)((long)a+((long)b*-1));
    }

    public int multiply(int a, int b) {
        return (int) Math.multiplyExact((long)a,(long)b);
    }

    public int divide(int a, int b) {
        return (int) (a/b);
    }
}

class Interview_16_10{
    public void process(int[] counts,int start,int end) {
        for (int i=start;i<=end;i++) counts[i]++;
    }
    public int maxAliveYear(int[] birth, int[] death) {
        int[] counts=new int[101];
        for (int i=0;i<birth.length;i++) {
            int start=birth[i],end=death[i];
            process(counts,start-1900,end-1900+1);
        }
        int maxCount=0,year=0;
        for (int i=0;i<counts.length;i++) {
            if (maxCount<counts[i]) {
                maxCount=counts[i];
                year=i;
            }
        }
        year=year+1900;
        return year;
    }
}

class Interview_16_11{
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) return new int[0];
        if (shorter == longer) return new int[]{shorter * k};
        int[] lengths = new int[k + 1];
        for (int i = 0; i <= k; i++) {
            lengths[i] = shorter * (k - i) + longer * i;
        }
        return lengths;
    }
}

class Interview_16_13{
    public double[] cutSquares(int[] square1, int[] square2) {
        return null;
    }
}

class Interview_16_14{}

class Interview_16_15{
    public int[] masterMind(String solution, String guess) {
        int l=solution.length();
        int[] ans=new int[2];
        Map<Character, Integer> map1=new HashMap<Character, Integer>();
        Map<Character, Integer> map2=new HashMap<Character, Integer>();
        for(int i=0;i<l;i++){
            if(solution.charAt(i)==guess.charAt(i)) ans[0]++;
            else{
                map1.put(solution.charAt(i), map1.getOrDefault(solution.charAt(i), 0)+1);
                map2.put(guess.charAt(i), map2.getOrDefault(guess.charAt(i), 0)+1);
            }
        }
        for(char c:map2.keySet()){
            if(map1.containsKey(c)) ans[1]+=map2.get(c)>map1.get(c) ? map1.get(c) : map2.get(c);
        }
        return ans;
    }
}

class Interview_16_16{
    public int[] subSort(int[] array) {
        int start=-1,end=-1;
        int max=Integer.MIN_VALUE,min=Integer.MAX_VALUE;
        for (int i=0;i<array.length;i++) {//当某个数之后存在比该数小的数那么小数需被排序
            if (array[i]>=max) max=array[i];//得到0~i区间内最大的数
            else end=i;
        }
        for (int i=array.length-1;i>=0;i--) {//当某个数之前存在比该数打的数那么大数需被排序
            if (array[i]<=min) min=array[i];//得到i~length-1区间内最小的数
            else start=i;
        }
        return new int[]{start,end};
    }
}

class Interview_16_17{
    public int maxSubArray(int[] nums) {
        int maxSum=nums[0],sum=nums[0];
        for (int i=1;i< nums.length;i++) {
            if (sum<0) sum=nums[i];
            else sum+=nums[i];
            maxSum=Math.max(maxSum,sum);
        }
        maxSum=Math.max(maxSum,sum);
        return maxSum;
    }
}

class Interview_16_19{
    public int[] pondSizes(int[][] land) {
        int count=0;
        ArrayList<Integer> resList=new ArrayList<>();
        for(int i=0;i<land.length;i++){
            for(int j=0;j<land[0].length;j++){
                if(land[i][j]==0){
                    count= process(land, i, j);
                    resList.add(count);
                }
            }
        }
        int[] result=new int[resList.size()];
        for(int i=0;i<resList.size();i++) result[i]=resList.get(i);
        Arrays.sort(result);
        return result;
    }
    public int process(int[][] land, int i, int j){
        if(i<0 || i>=land.length || j<0 || j>=land[0].length || land[i][j]!=0) return 0;
        land[i][j]=-1;
        int count=1;
        count+= process(land, i+1, j);//下
        count+= process(land, i-1, j);//上
        count+= process(land, i, j+1);//右
        count+= process(land, i, j-1);//左
        count+= process(land, i+1, j+1);//右下
        count+= process(land, i-1, j+1);//右上
        count+= process(land, i-1, j-1);//左上
        count+= process(land, i+1, j-1);//左下
        return count;
    }
}

class Interview_16_20{
    public boolean process(List<Set<Character>> list,String num,String curStr) {
        if (num.length()!=curStr.length()) return false;
        char[] chars=curStr.toCharArray(),nums=num.toCharArray();
        for (int i=0;i<curStr.length();i++) {
            Set<Character> curSet=list.get((nums[i]-'0')-2);
            if (!curSet.contains(chars[i])) return false;
        }
        return true;
    }
    public List<String> getValidT9Words(String num, String[] words) {
        Set<Character> set2=new HashSet<>(),set3=new HashSet<>(),set4=new HashSet<>(),set5=new HashSet<>(),
                set6=new HashSet<>(),set7=new HashSet<>(),set8=new HashSet<>(),set9=new HashSet<>();
        set2.add('a');
        set2.add('b');
        set2.add('c');
        set3.add('d');
        set3.add('e');
        set3.add('f');
        set4.add('g');
        set4.add('h');
        set4.add('i');
        set5.add('j');
        set5.add('k');
        set5.add('l');
        set6.add('m');
        set6.add('n');
        set6.add('o');
        set7.add('p');
        set7.add('q');
        set7.add('r');
        set7.add('s');
        set8.add('t');
        set8.add('u');
        set8.add('v');
        set9.add('w');
        set9.add('x');
        set9.add('y');
        set9.add('z');
        List<Set<Character>> list=new ArrayList<>();
        list.add(set2);
        list.add(set3);
        list.add(set4);
        list.add(set5);
        list.add(set6);
        list.add(set7);
        list.add(set8);
        list.add(set9);
        List<String> result=new ArrayList<>();
        for (String str : words) {
            if (process(list,num,str)) {
                result.add(str);
            }
        }
        return result;
    }
}

class Interview_16_22{
    public class Position {
        int x, y;// 横坐标 x 纵坐标 y

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == this) return true;
            if (!(obj instanceof Position)) return false;
            Position o = (Position) obj;
            return x == o.x && y == o.y;
        }

        @Override
        public int hashCode() {// 改写哈希算法，使两个 Position 对象可以比较坐标而不是内存地址
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }

    public List<String> printKMoves(int K) {
        char[] direction = {'L', 'U', 'R', 'D'};
        // 用“向量”记录方向，顺序与上一行方向的字符顺序保持一致，每个元素的后一个元素都是可以90°向右变换得到的
        int[][] offset = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        // 蚂蚁的位置
        Position antPos = new Position(0, 0);
        // 蚂蚁方向的向量序号
        int antDir = 2;
        // 用集合存储所有黑块的坐标，一开始想再定义一个路径的坐标集合，发现可以直接用黑块+蚂蚁位置也能过
        Set<Position> blackSet = new HashSet<>();
        while (K > 0) {
            // 新的坐标对象用于放入集合
            Position t = new Position(antPos.x, antPos.y);
            // 如果黑块集合能存入，说明脚下的块不在集合中，也就意味着是白色，方向序号循环自增1
            if (blackSet.add(t)) antDir = (antDir + 1) % 4;
            else {
                // 否则说明脚下的块已经在集合中，也就意味着是黑色，方向序号循环自增3，相当于自减1，但是Math.floorMod取模可能消耗大？用+3替代
                antDir = (antDir + 3) % 4;
                blackSet.remove(t);// 将黑块变白
            }
            // 蚂蚁移动位置
            antPos.x += offset[antDir][0];
            antPos.y += offset[antDir][1];
            K--;
        }
        // 计算边界，即输出网格的行数和列数
        int left = antPos.x, top = antPos.y, right = antPos.x, bottom = antPos.y;
        for (Position pos : blackSet) {
            left = pos.x < left ? pos.x : left;
            top = pos.y < top ? pos.y : top;
            right = pos.x > right ? pos.x : right;
            bottom = pos.y > bottom ? pos.y : bottom;
        }
        char[][] grid = new char[bottom - top + 1][right - left + 1];
        for (char[] row : grid)// 填充白块
            Arrays.fill(row, '_');
        for (Position pos : blackSet)// 替换黑块
            grid[pos.y - top][pos.x - left] = 'X';
        grid[antPos.y - top][antPos.x - left] = direction[antDir];// 替换蚂蚁
        List<String> result = new ArrayList<>();// 利用网格生成字符串列表
        for (char[] row : grid)
            result.add(String.valueOf(row));
        return result;
    }
}

class Interview_16_24{
    public List<List<Integer>> pairSums(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums == null || nums.length == 0) return list;
        int n = nums.length;
        Arrays.sort(nums);
        int left = 0;
        int right = n - 1;
        while (left < right) {
            int x = nums[left];
            int y = nums[right];
            if (x + y == target) {
                List<Integer> temp = new ArrayList<>();
                temp.add(x);
                temp.add(y);
                list.add(temp);
                left++;
                right--;
            } else if (x + y > target) right--;
            else left++;
        }
        return list;
    }
}

class Interview_16_25{
    public HashMap<Integer,Integer> hashMap=new HashMap<>();
    public Deque<Info> infos1=new ArrayDeque<>();
    public HashMap<Integer,Info> hashMap1=new HashMap<>();
    public int capacity;
    public static class Info{
        int key;
        int time;
        public Info(int key, int time) {
            this.key = key;
            this.time = time;
        }
    }
    public Interview_16_25(int capacity) {
        this.capacity=capacity;
    }
    public int get(int key) {
        if (hashMap.containsKey(key)){
            Integer integer = hashMap.get(key);
            Info info = hashMap1.get(key);
            infos1.remove(info);
            info.time= Math.toIntExact(System.currentTimeMillis()>>11);
            infos1.addLast(info);
            return integer;
        }else {
            return -1;
        }
    }
    public void put(int key, int value) {
        if (hashMap.size()==capacity&&!hashMap.containsKey(key)){
            Info poll = infos1.pollFirst();
            hashMap.remove(poll.key);
            hashMap1.remove(poll.key);
            Info info = new Info(key, Math.toIntExact(System.currentTimeMillis()>>11));
            hashMap1.put(key,info);
            hashMap.put(key,value);
            infos1.addLast(info);
        }else {
            if (hashMap.containsKey(key)){
                hashMap.put(key,value);
                Info info = hashMap1.get(key);
                infos1.remove(info);
                info.time= (int) System.currentTimeMillis()>>11;
                infos1.addLast(info);
            }else {
                Info info = new Info(key, Math.toIntExact(System.currentTimeMillis()>>11));
                hashMap1.put(key,info);
                hashMap.put(key,value);
                infos1.addLast(info);
            }
        }
    }
}

class Interview_16_26{
    public int calculate(String s) {
        List<String> list=new ArrayList<>();
        StringBuffer temp=new StringBuffer();
        char[] str=s.toCharArray();
        for (int i=0;i<s.length();i++) {
            if (str[i]==' ') continue;//空格跳过
            else if (str[i]>='0'&&str[i]<='9') {//拼接数字
                temp.append(str[i]);
            }else {//运算符添加
                list.add(temp.toString());//添加数字
                list.add(String.valueOf(str[i]));//添加运算符
                temp=new StringBuffer();//重置拼接数字
            }
        }
        list.add(temp.toString());//添加最后一个数字
        while (list.contains("/")||list.contains("*")) {//先乘除
            int d=list.indexOf("/"),m=list.indexOf("*");
            int first=-1;
            if (d==-1||m==-1) first= d==-1 ? m : d;
            else first= d<m ? d :m;
            if (first!=-1) {
                Integer num1=Integer.valueOf(list.get(first-1)),num2=Integer.valueOf(list.get(first+1));
                int result=0;
                if (list.get(first).equals("/")) result=num1/num2;
                else result=num1*num2;
                list.remove(first+1);
                list.remove(first);
                list.remove(first-1);
                list.add(first-1,String.valueOf(result));
            }
        }
        int result=Integer.valueOf(list.get(0));
        for (int i=1;i<list.size();) {
            if (list.get(i).equals("+")) result=result+Integer.valueOf(list.get(i+1));
            else result=result-Integer.valueOf(list.get(i+1));
            i+=2;
        }
        return result;

//        法二
//        Deque<Integer> stack = new ArrayDeque<Integer>();
//        char preSign = '+';
//        int num = 0;
//        int n = s.length();
//        for (int i = 0; i < n; ++i) {
//            if (Character.isDigit(s.charAt(i))) {
//                num = num * 10 + s.charAt(i) - '0';
//            }
//            if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
//                switch (preSign) {
//                    case '+':
//                        stack.push(num);
//                        break;
//                    case '-':
//                        stack.push(-num);
//                        break;
//                    case '*':
//                        stack.push(stack.pop() * num);
//                        break;
//                    default:
//                        stack.push(stack.pop() / num);
//                }
//                preSign = s.charAt(i);
//                num = 0;
//            }
//        }
//        int ans = 0;
//        while (!stack.isEmpty()) {
//            ans += stack.pop();
//        }
//        return ans;
    }
}